from collections import deque
from tools.treeNode import Tree


def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    p_queue = deque([p])
    q_queue = deque([q])
    while p_queue and q_queue:
        p_node = p_queue.popleft()
        q_node = q_queue.popleft()
        if p_node.val != q_node.val:
            return False
        p_left = p_node.left
        p_right = p_node.right
        q_left = q_node.left
        q_right = q_node.right
        if (not p_left) ^ (not q_left):
            return False
        if (not p_right) ^ (not q_right):
            return False
        if p_left:
            p_queue.append(p_left)
        if p_right:
            p_queue.append(p_right)
        if q_left:
            q_queue.append(q_left)
        if q_right:
            q_queue.append(q_right)
    return (not p_queue) and (not q_queue)


p = Tree(1)
p.left = Tree(2)

q = Tree(1)
q.right = Tree(2)
print(isSameTree(p, q))
